import java.util.*;

public class Test66 {
    public static void main(String[] args) {
        Stack stack = new Stack<>();
        stack.empty();
    }
    public int maxArea(int[] height) {
        int max = 0;
        int left = 0;
        int right = height.length-1;
        while(left < right){



            int temp = (right - left)*(height[left] < height[right]?height[left++]:height[right--]);
            max = Math.max(temp,max);
        }
        return max;
    }
    //翻转链表
//    public ListNode reverseList(ListNode head) {
//        if(head == null || head.next == null) return head;
//        ListNode newHead = reverseList(head.next);
//        head.next.next = head;
//        head.next = null;
//        return newHead;
//    }
//    public List<List<Integer>> zigzagLevelOrder(TreeNode root)
// {
//         List<List<Integer>> ret = new ArrayList<>();
//         if(root == null) return ret;
//         Queue<TreeNode> q = new LinkedList<>();
//         q.add(root);
//         int level = 1;
//
//         while(!q.isEmpty())
//             {
//             int sz = q.size();
//             List<Integer> tmp = new ArrayList<>();
//             for(int i = 0; i < sz; i++)
//                 {
//                 TreeNode t = q.poll();
//                 tmp.add(t.val);
//                 if(t.left != null) q.add(t.left);
//                 if(t.right != null) q.add(t.right);
//                 }
//             // 判断是否逆序
//             if(level % 2 == 0) Collections.reverse(tmp);
//             ret.add(tmp);
//             level++;
//             }
//
//         return ret;
//         }
//    public List<List<Integer>> levelOrder(Node root)
// {
//         List<List<Integer>> ret = new ArrayList<>();
//         if(root == null) return ret;
//         Queue<Node> q = new LinkedList<>();
//         q.add(root);
//
//         while(!q.isEmpty())
//             {
//             int sz = q.size();
//             List<Integer> tmp = new ArrayList<>(); // 统计本层的结点信息
//             for(int i = 0; i < sz; i++)
//                 {
//                 Node t = q.poll();
//                 tmp.add(t.val);
//                 for(Node child : t.children) // 让孩⼦⼊队
//                     {
//                     if(child != null)
//                         q.add(child);
//                     }
//                 }
//             ret.add(tmp);
//             }
//
//         return ret;
//         }
//         public boolean validateStackSequences(int[] pushed, int[] popped)
//         {
//         Stack<Integer> st = new Stack<>();
//         int i = 0, n = popped.length;
//         for(int x : pushed)
//             {
//             st.push(x);
//             while(!st.isEmpty() && st.peek() == popped[i])
//                 {
//                 st.pop();
//                 i++;
//                 }
//             }
//         return i == n;
//         }
//    public String decodeString(String _s)
// {
//         Stack<StringBuffer> st = new Stack<>();
//         st.push(new StringBuffer()); // 先放⼀个空串进去
//         Stack<Integer> nums = new Stack<>();
//
//         int i = 0, n = _s.length();
//         char[] s = _s.toCharArray();
//
//         while(i < n)
//             {
//             if(s[i] >= '0' && s[i] <= '9')
//                 {
//                 int tmp = 0;
//                 while(i < n && s[i] >= '0' && s[i] <= '9')
//                     {
//                     tmp = tmp * 10 + (s[i] - '0');
//                     i++;
//                     }
//                 nums.push(tmp);
//                 }
//             else if(s[i] == '[')
//                 {
//                 i++; // 把后⾯的字符串提取出来
//                 StringBuffer tmp = new StringBuffer();
//                 while(i < n && s[i] >= 'a' && s[i] <= 'z')
//                     {
//                     tmp.append(s[i]);
//                     i++;
//                     }
//                 st.push(tmp);
//                 }
//             else if(s[i] == ']')
//                 {
//                 // 解析
//                 StringBuffer tmp = st.pop();
//                 int k = nums.pop();
//
//                 while(k-- != 0)
//                     {
//                     st.peek().append(tmp);
//                     }
//                 i++;
//                 }
//             else
//             {
//                 StringBuffer tmp = new StringBuffer();
//                 while(i < n && s[i] >= 'a' && s[i] <= 'z')
//                     {
//                     tmp.append(s[i]);
//                     i++;
//                     }
//                 st.peek().append(tmp);
//                 }
//             }
//         return st.peek().toString();
//         }
//    public int calculate(String _s)
// {
//         Deque<Integer> st = new ArrayDeque<>();
//         char op = '+';
//         int i = 0, n = _s.length();
//         char[] s = _s.toCharArray();
//
//         while(i < n)
//             {
//             if(s[i] == ' ') i++;
//             else if(s[i] >= '0' && s[i] <= '9')
//                 {
//                 int tmp = 0;
//                 while(i < n && s[i] >= '0' && s[i] <= '9')
//                     {
//                     tmp = tmp * 10 + (s[i] - '0');
//                     i++;
//                     }
//                 if(op == '+') st.push(tmp);
//                 else if(op == '-') st.push(-tmp);
//                 else if(op == '*') st.push(st.pop() * tmp);
//                 else st.push(st.pop() / tmp);
//                 }
//             else
//             {
//                 op = s[i];
//                 i++;
//                 }
//             }
//         // 统计结果
//         int ret = 0;
//         while(!st.isEmpty())
//             {
//             ret += st.pop();
//             }
//         return ret;
//         }
//    PriorityQueue<Integer> left;
//    PriorityQueue<Integer> right;
//
//         public MedianFinder()
// {
//         left = new PriorityQueue<Integer>((a, b) -> b - a); // ⼤根堆
//         right = new PriorityQueue<Integer>((a, b) -> a - b); // ⼩根堆
//         }
//
//         public void addNum(int num)
// {
//         // 分情况讨论
//         if(left.size() == right.size())
//             {
//             if(left.isEmpty() || num <= left.peek())
//                 {
//                 left.offer(num);
//                 }
//             else
//             {
//                 right.offer(num);
//                 left.offer(right.poll());
//                 }
//             }
//         else
//         {
//             if(num <= left.peek())
//                {
//                 left.offer(num);
//                 right.offer(left.poll());
//                 }
//             else
//             {
//                 right.offer(num);
//                 }
//             }
//         }
//
//         public double findMedian()
// {
//         if(left.size() == right.size()) return (left.peek() + right.peek()) / 2.
//         else return left.peek();
//         }
    public boolean backspaceCompare(String s, String t)
 {
         return changeStr(s).equals(changeStr(t));
         }
         public String changeStr(String s)
 {
         StringBuffer ret = new StringBuffer(); // ⽤数组模拟栈结构
         for(int i = 0; i < s.length(); i++)
             {
             char ch = s.charAt(i);
             if(ch != '#')
                 {
                 ret.append(ch); // ⼊栈
                 }
             else
             {
                 if(ret.length() > 0) ret.deleteCharAt(ret.length() - 1); // 出栈
                 }
             }
         return ret.toString();
         }
//    public String removeDuplicates(String _s)
//    {
//        StringBuffer ret = new StringBuffer(); // ⽤数组来模拟栈结构
//        char[] s = _s.toCharArray();
//        for(char ch : s)
//        {
//            if(ret.length() > 0 && ch == ret.charAt(ret.length() - 1))
//            {
//// 出栈
//                ret.deleteCharAt(ret.length() - 1);
//            }
//            else
//            {
//// 进栈
//                ret.append(ch);
//            }
//        }
//        return ret.toString();
//    }
    public static void main6(String[] args) {
        char ch = ' ';
    }
    public static void main7(String[] args) {
        char[] ch = new char[2];
        System.out.println(ch[0]);
    }
//    public String multiply(String num1, String num2)
// {
//         int m = num1.length(), n = num2.length();
//         char[] n1 = new StringBuffer(num1).reverse().toString().toCharArray();
//         char[] n2 = new StringBuffer(num2).reverse().toString().toCharArray();
//
//         int[] tmp = new int[m + n - 1];
//
//         // 1. ⽆进位相乘后相加
//         for(int i = 0; i < m; i++)
//             for(int j = 0; j < n; j++)
//             tmp[i + j] += (n1[i] - '0') * (n2[j] - '0');
//
//         // 2. 处理进位
//         int cur = 0, t = 0;
//         StringBuffer ret = new StringBuffer();
//         while(cur < m + n - 1 || t != 0)
//             {
//             if(cur < m + n - 1) t += tmp[cur++];
//            ret.append((char)(t % 10 + '0'));
//            t /= 10;
//        }
//// 3. 处理进位
//        while(ret.length() > 1 && ret.charAt(ret.length() - 1) == '0')
//            ret.deleteCharAt((ret.length() - 1));
//        return ret.reverse().toString();
//    }
//    public String addBinary(String a, String b)
// {
//         StringBuffer ret = new StringBuffer();
//         int cur1 = a.length() - 1, cur2 = b.length() - 1, t = 0;
//         while(cur1 >= 0 || cur2 >= 0 || t != 0)
//             {
//             if(cur1 >= 0) t += a.charAt(cur1--) - '0';
//             if(cur2 >= 0) t += b.charAt(cur2--) - '0';
//             ret.append((char)('0' + (char)(t % 2)));
//             t /= 2;
//             }
//         ret.reverse();
//         return ret.toString();
//         }
//    public String longestPalindrome(String s)
// {
//         int begin = 0, len = 0, n = s.length();
//         for(int i = 0; i < n; i++) // 固定所有的中间点
//             {
//             // 先扩展奇数⻓度的⼦串
//             int left = i, right = i;
//             while(left >= 0 && right < n && s.charAt(left) == s.charAt(right))
//                 {
//                 left--;
//                 right++;
//                 }
//             if(right - left - 1 > len)
//                 {
//                 begin = left + 1;
//                 len = right - left - 1;
//                 }
//             // 扩展偶数⻓度
//             left = i; right = i + 1;
//             while(left >= 0 && right < n && s.charAt(left) == s.charAt(right))
//                 {
//                 left--;
//                 right++;
//                 }
//             if(right - left - 1 > len)
//                 {
//                 begin = left + 1;
//                 len = right - left - 1;
//                 }
//             }
//         return s.substring(begin, begin + len);
//         }
//    public int[] twoSum(int[] nums, int target)
//    {
//        Map<Integer, Integer> hash = new HashMap<>(); // <nums[i], i>
//        for(int i = 0; i < nums.length; i++)
//        {
//            int x = target - nums[i];
//            if(hash.containsKey(x))
//            {
//                return new int[]{i, hash.get(x)};
//            }
//            hash.put(nums[i], i);
//        }
//        // 照顾编译器
//        return new int[]{-1, -1};
//    }
//    public ListNode reverseKGroup(ListNode head, int k)
// {
//         // 1. 先求出需要逆序多少组
//         int n = 0;
//         ListNode cur = head;
//         while(cur != null)
//             {
//             cur = cur.next;
//             n++;
//             }
//         n /= k;
//
//         // 2. 重复 n 次：⻓度为 k 的链表的逆序
//         ListNode newHead = new ListNode(0);
//         ListNode prev = newHead;
//         cur = head;
//
//         for(int i = 0; i < n; i++)
//             {
//            ListNode tmp = cur;
//            for(int j = 0; j < k; j++)
//            {
//// 头插的逻辑
//                ListNode next = cur.next;
//                cur.next = prev.next;
//                prev.next = cur;
//                cur = next;
//            }
//            prev = tmp;
//        }
//// 把后⾯不需要逆序的部分连接上
//        prev.next = cur;
//        return newHead.next;
//    }
//    public ListNode mergeKLists(ListNode[] lists)
// {
//         return merge(lists, 0, lists.length - 1);
//         }
//
//         public ListNode merge(ListNode[] lists, int left, int right)
// {
//         if(left > right) return null;
//         if(left == right) return lists[left];
//
//         // 1. 平分数组
//         int mid = (left + right) / 2;
//         // [left, mid] [mid + 1, right]
//
//         // 2. 递归处理左右两部分
//         ListNode l1 = merge(lists, left, mid);
//         ListNode l2 = merge(lists, mid + 1, right);
//
//         // 3. 合并两个有序链表
//         return mergeTwoList(l1, l2);
//         }
//
//         public ListNode mergeTwoList(ListNode l1, ListNode l2)
// {
//         if(l1 == null) return l2;
//         if(l2 == null) return l1;
//
//         // 合并两个有序链表
//         ListNode head = new ListNode(0);
//         ListNode cur1 = l1, cur2 = l2, prev = head;
//
//         while(cur1 != null && cur2 != null)
//             {
//             if(cur1.val <= cur2.val)
//                 {
//                 prev.next = cur1;
//                 prev = cur1;
//                 cur1 = cur1.next;
//                 }
//             else
//             {
//                54 prev.next = cur2;
//                prev = cur2;
//                cur2 = cur2.next;
//            }
//        }
//        if(cur1 != null) prev.next = cur1;
//        if(cur2 != null) prev.next = cur2;
//        return head.next;
//    }
//     public ListNode mergeKLists(ListNode[] lists)
// {
//         PriorityQueue<ListNode> heap = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
//
//                 // 将所有头结点加⼊到⼩根堆中
//                 for(ListNode l : lists)
//             if(l != null)
//             heap.offer(l);
//
//         // 合并
//         ListNode ret = new ListNode(0);
//         ListNode prev = ret;
//         while(!heap.isEmpty())
//             {
//             ListNode t = heap.poll();
//             prev.next = t;
//             prev = t;
//             if(t.next != null) heap.offer(t.next);
//             }
//
//         return ret.next;
//         }
//    {
//        public ListNode swapPairs(ListNode head)
//        {
//        if(head == null || head.next == null) return head;
//        ListNode newHead = new ListNode(0);
//        newHead.next = head;
//        ListNode prev = newHead, cur = prev.next, next = cur.next, nnext = next.
//        while(cur != null && next != null)
//        {
//        // 交换节点
//            prev.next = next;
//            next.next = cur;
//            cur.next = nnext;
//            // 修改指针,下面两句不能搞混
//            prev = cur; // 注意顺序
//            cur = nnext;
//            if(cur != null) next = cur.next;
//            if(next != null) nnext = next.next;
//            }
//
//         return newHead.next;
//         }
//    int[] tmp;
//    public int reversePairs(int[] nums)
//    {
//        int n = nums.length;
//        tmp = new int[n];
//        return mergeSort(nums, 0, n - 1);
//    }
//    public int mergeSort(int[] nums, int left, int right)
//    {
//        if(left >= right) return 0;
//        int ret = 0;
//        // 1. 根据中间元素，将区间分成两部分
//        int mid = (left + right) / 2;
//        // [left, mid] [mid + 1, right]
//        // 2. 求出左右两个区间的翻转对
//        ret += mergeSort(nums, left, mid);
//        ret += mergeSort(nums, mid + 1, right);
//        // 3. 处理⼀左⼀右 - 先计算翻转对
//        int cur1 = left, cur2 = mid + 1, i = left;
//        // 升序版本
//        while(cur2 <= right)
//        {
//            while(cur1 <= mid && nums[cur2] >= nums[cur1] / 2.0) cur1++;
//            if(cur1 > mid)
//                break;
//            ret += mid - cur1 + 1;
//            cur2++;
//        }
//         // 4. 合并两个有序数组 - 升序
//             cur1 = left; cur2 = mid + 1;
//             while(cur1 <= mid && cur2 <= right)
//             tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
//             while(cur1 <= mid) tmp[i++] = nums[cur1++];
//             while(cur2 <= right) tmp[i++] = nums[cur2++];
//
//             for(int j = left; j <= right; j++)
//             nums[j] = tmp[j];
//
//             return ret;
//         }
//    int[] tmp;
//    public int reversePairs(int[] nums)
//    {
//        int n = nums.length;
//        tmp = new int[n];
//        return mergeSort(nums, 0, n - 1);
//    }
//    public int mergeSort(int[] nums, int left, int right)
//    {
//        if(left >= right) return 0;
//        int ret = 0;
//        // 1. 根据中间元素，将区间分成两部分
//        int mid = (left + right) / 2;
//        // [left, mid] [mid + 1, right]
//        // 2. 求出左右两个区间的翻转对
//        ret += mergeSort(nums, left, mid);
//        ret += mergeSort(nums, mid + 1, right);
//        // 3. 处理⼀左⼀右 - 先计算翻转对
//        int cur1 = left, cur2 = mid + 1, i = left;
//        // 降序版本
//        while(cur1 <= mid)
//        {
//            while(cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) cur2++;
//            if(cur2 > right)
//                break;
//            ret += right - cur2 + 1;
//            cur1++;
//        }
//        // 4. 合并两个有序数组
//        cur1 = left; cur2 = mid + 1;
//        while(cur1 <= mid && cur2 <= right)
//            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur2++] : nums[cur1++];
//        while(cur1 <= mid) tmp[i++] = nums[cur1++];
//        while(cur2 <= right) tmp[i++] = nums[cur2++];
//        for(int j = left; j <= right; j++)
//            nums[j] = tmp[j];
//
//        return ret;
//    }
//    int[] ret;
//    int[] index; // 标记 nums 中当前元素的原始下标
//    int[] tmpIndex;
//    int[] tmpNums;
//    public List<Integer> countSmaller(int[] nums)
//    {
//        int n = nums.length;
//        ret = new int[n];
//        index = new int[n];
//        tmpIndex = new int[n];
//        tmpNums = new int[n];
//        // 初始化 index 数组
//        for(int i = 0; i < n; i++)
//            index[i] = i;
//        mergeSort(nums, 0, n - 1);
//        List<Integer> l = new ArrayList<Integer>();
//        for(int x : ret)
//            l.add(x);
//        return l;
//    }
//    public void mergeSort(int[] nums, int left, int right)
//    {
//        if(left >= right) return;
//        // 1. 根据中间元素划分区间
//        int mid = (left + right) / 2;
//        // [left, mid] [mid + 1, right]
//        // 2. 处理左右两个区间
//        mergeSort(nums, left, mid);
//        mergeSort(nums, mid + 1, right);
//        // 3. 处理⼀左⼀右的情况
//        int cur1 = left, cur2 = mid + 1, i = 0;
//        while(cur1 <= mid && cur2 <= right) // 降序排序
//        {
//            if(nums[cur1] <= nums[cur2])
//            {
//                tmpNums[i] = nums[cur2];
//                tmpIndex[i++] = index[cur2++];
//            }
//            else
//            {
//                ret[index[cur1]] += right - cur2 + 1; // 重点
//                tmpNums[i] = nums[cur1];
//                tmpIndex[i++] = index[cur1++];
//            }
//        }
//        // 4. 处理剩余的排序⼯作
//        while(cur1 <= mid)
//        {
//            tmpNums[i] = nums[cur1];
//            tmpIndex[i++] = index[cur1++];
//        }
//        while(cur2 <= right)
//        {
//            tmpNums[i] = nums[cur2];
//            tmpIndex[i++] = index[cur2++];
//        }
//        for(int j = left; j <= right; j++)
//        {
//            nums[j] = tmpNums[j - left];
//            index[j] = tmpIndex[j - left];
//        }
//    }
//    int[] tmp;
//    public int reversePairs(int[] nums)
//    {
//        int n = nums.length;
//        tmp = new int[n];
//        return mergeSort(nums, 0, n - 1);
//    }
//    public int mergeSort(int[] nums, int left, int right)
//    {
//        if(left >= right) return 0;
//        int ret = 0;
//        // 1. 选择⼀个中间点，将数组划分成两部分
//        int mid = (left + right) / 2;
//        // [left, mid] [mid + 1, right]
//        // 2. 左半部分的个数 + 排序 + 右半部分的个数 + 排序
//        ret += mergeSort(nums, left, mid);
//        ret += mergeSort(nums, mid + 1, right);
//        // 3. ⼀左⼀右的个数
//        int cur1 = left, cur2 = mid + 1, i = 0;
//        while(cur1 <= mid && cur2 <= right) // 升序版本
//        {
//            if(nums[cur1] <= nums[cur2])
//            {
//                tmp[i++] = nums[cur1++];
//            }
//            else
//            {
//                ret += mid - cur1 + 1;
//                tmp[i++] = nums[cur2++];
//            }
//        }
//        // 4. 处理⼀下排序
//        while(cur1 <= mid) tmp[i++] = nums[cur1++];
//        while(cur2 <= right) tmp[i++] = nums[cur2++];
//        for(int j = left; j <= right; j++)
//            nums[j] = tmp[j - left];
//
//        return ret;
//    }
//    int[] tmp;
//    public int[] sortArray(int[] nums)
//    {
//        tmp = new int[nums.length];
//        mergeSort(nums, 0, nums.length - 1);
//        return nums;
//    }
//    public void mergeSort(int[] nums, int left, int right)
//    {
//        if(left >= right) return;
//        // 1. 根据中间点划分区间
//        int mid = (left + right) / 2;
//        // [left, mid] [mid + 1, right]
//        // 2. 先把左右区间排个序
//        mergeSort(nums, left, mid);
//        mergeSort(nums, mid + 1, right);
//        // 3. 合并两个有序数组
//        int cur1 = left, cur2 = mid + 1, i = 0;
//        while(cur1 <= mid && cur2 <= right)
//            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
//        // 处理没有遍历完的数组
//        while(cur1 <= mid) tmp[i++] = nums[cur1++];
//        while(cur2 <= right) tmp[i++] = nums[cur2++];
//        // 4. 还原
//        for(int j = left; j <= right; j++)
//            nums[j] = tmp[j - left];
//    }
    //子集问题
    List<List<Integer>> ret;
    List<Integer> path;
    public List<List<Integer>> subsets(int[] nums) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        dfs(nums,0);
        return ret;
    }
    void dfs(int[] nums,int pos){
        if(pos == nums.length){
            ret.add(new ArrayList<>(path));
            return;
        }
        //选择
        path.add(nums[pos]);
        dfs(nums,pos+1);
        path.remove(path.size()-1);
        //不选
        dfs(nums,pos+1);

    }
    //有效的数独问题
    public boolean isValidSudoku(char[][] board) {
        //定义标记数组 , 下面表示每一行是否出现了某一个数字
        //一定要多开一个空间 , 否则会越界
        boolean[][] row = new boolean[9][10];
        boolean[][] col = new boolean[9][10];
        boolean[][][] grid = new boolean[3][3][10];
        for(int i = 0;i<9;i++){
            for(int j = 0;j<9;j++){
                //前提条件要从数字中选择
                if(board[i][j] != '.'){
                    int num = board[i][j] - '0';
                    //判断数独是否有效
                    if(row[i][num] || col[j][num] || grid[i/3][j/3][num]){
                        return false;
                    } else{
                        row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;
                    }
                }

            }
        }
        return true;
    }
    public static void main4(String[] args) {
        //通过new放在堆上
        String str1 = "123";
        String str2 = new String(str1);
        System.out.println(str1 == str2);
    }
    public static void main3(String[] args) {
        //直接赋值是放在常量池
        String str1 = "123";
        String str2 = "123";
        System.out.println(str1 == str2);
    }
    public static void main2(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = sc.nextInt();
        int[][] arr = new int[n][n];
        boolean[][] sta = new boolean[n][n];
        int flag = 1;//三个蛇形状态
        int flag2 = 1;
        int i = 0;int j = 0;
        int count = 1;
        while(count < n*n && sta[n-1][n-1] == false){
            flag = 1;
            if(flag == 1 && i == 0){
                if(i <=n && j <=n && sta[i][j] == false){
                    arr[i][j] = (count++);
                    sta[i][j] = true;
                    // flag = 2;
                    flag2 = 2;
                }
                if(i <=n && j+1 <=n && sta[i][j+1] == false ){
                    j++;
                    arr[i][j] = (count++);
                    sta[i][j] = true;
                    // flag = 2;
                    flag2 = 2;
                }
                flag = 2;

            }
            while(flag == 2 && i+1<=n && j-1 <=n && j-1>0){
                i--;
                j--;
                arr[i][j] = (count++);
                sta[i][j] = true;
            }
            flag = 3;
            if(i + 1 < n && j < n && sta[i][j+1] == false && flag == 3){
                i++;
                arr[i][j] = (count++);
                sta[i][j] = true;
                // flag = 2;
                flag2 = 2;
            }
            flag = 4;
            while(flag == 4 && i-1< n && i-1>0 && j+1 < n ){
                i--;
                j++;
                arr[i][j] = (count++);
                sta[i][j] = true;
            }


        }
        for(int z = 0;z< n;z++){
            for(int x = 0;x< n;x++){
                System.out.print(arr[z][x]);
            }
            System.out.println();
        }
    }
    public static void main1(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (sc.hasNext()) { // 注意 while 处理多个 case
            int m = sc.nextInt();
            int k = sc.nextInt();
            int[] arr1 = new int[m];
            int[] arr2 = new int[m];
            for(int i = 0;i<m;i++){
                arr1[i] = sc.nextInt();

            }
            for(int j = 0;j<m;j++){
                arr2[j] = sc.nextInt();
            }
            int[] temp = new int[m*m];
            int q = 0;
            for(int i = 0;i<m;i++){
                for(int j = 0;j<m;j++){
                    temp[q++] = arr1[i] + arr2[j];
                }
            }
            Arrays.sort(temp);
            int w = m*m-1;
            while(k-->0){
                System.out.print(temp[w--]+" ");
            }
        }
    }
}
